/* JavaLog - package tracker 
 * 
 * Copyright (C) 2009 Allyson Lima, Diego Pedro, Victor Freire
 * 
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software 
 * Foundation, either version 3 of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 * PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with this 
 * program. If not, see <http://www.gnu.org/licenses/>.
 */

package br.edu.ufcg.ccc.javalog.allshortestpath;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import br.edu.ufcg.ccc.javalog.exceptions.LocationException;
import br.edu.ufcg.ccc.javalog.model.Franchise;

/**
 * FloydWarshall class
 * 
 * @author Allyson Lima, Diego Pedro, Victor Freire
 * @version 08/11/09
 */
public class FloydWarshall {

	private int[][] matrixDistance;
	private int[][] matrixAdjacency;

	private static int[][] arrayDistances = new int[1][1];
	private static int[] arrayNodes = new int[1];

	private List<Franchise> listAllFranchises;

	/**
	 * Calculates the shortest path from any pair of vertices
	 * 
	 * @param nodes
	 *            array with the vertices(starting with zero index)
	 * @param edges
	 *            array with the edges
	 */
	public void calcShortestPaths(int[] nodes, int[][] edges) {

		matrixDistance = edges;
		matrixAdjacency = new int[nodes.length][nodes.length];

		for (int k = 0; k < nodes.length; k++) {
			for (int i = 0; i < nodes.length; i++) {
				for (int j = 0; j < nodes.length; j++) {
					if (matrixDistance[i][k] != Integer.MAX_VALUE
							&& matrixDistance[k][j] != Integer.MAX_VALUE
							&& matrixDistance[i][k] + matrixDistance[k][j] < matrixDistance[i][j]) {
						matrixDistance[i][j] = matrixDistance[i][k]
								+ matrixDistance[k][j];
						matrixAdjacency[i][j] = nodes[k];
					}
				}
			}
		}
	}

	/**
	 * Returns shortest distance between two pairs of vertices
	 * 
	 * @param source
	 *            Source vertice
	 * @param target
	 *            Target vertice
	 * @return shortest distance between two pairs of vertices
	 */
	public int getShortestDistance(int source, int target) {
		return matrixDistance[source][target];
	}

	/**
	 * Returns shortest path between two pairs of vertices
	 * 
	 * @param source
	 *            Source vertice
	 * @param target
	 *            Target vertice
	 * @return shortest path between two pairs of vertices
	 */
	public ArrayList<Integer> getShortestPath(int source, int target) {
		if (matrixDistance[source][target] == Integer.MAX_VALUE) {
			return new ArrayList<Integer>();
		}
		ArrayList<Integer> path = getIntermediatePath(source, target);
		path.add(0, source);
		path.add(target);
		return path;
	}

	/**
	 * Returns intermediate shortest distance between two pairs of vertices
	 * 
	 * @param source
	 *            Source vertice
	 * @param target
	 *            Target vertice
	 * @return intermediate shortest distance between two pairs of vertices
	 */
	private ArrayList<Integer> getIntermediatePath(int source, int target) {
		if (matrixDistance == null) {
			throw new IllegalArgumentException(
					"Must call calcShortestPaths(...) "
							+ "before attempting to obtain a path.");
		}
		if (matrixAdjacency[source][target] == 0) {
			return new ArrayList<Integer>();
		}
		ArrayList<Integer> path = new ArrayList<Integer>();
		path
				.addAll(getIntermediatePath(source,
						matrixAdjacency[source][target]));
		path.add(matrixAdjacency[source][target]);
		path
				.addAll(getIntermediatePath(matrixAdjacency[source][target],
						target));
		return path;
	}

	/**
	 * Updates the array of distances algorithm floyd
	 * 
	 * @param nearClientStoresList
	 *            List of near franchises chosen by the client
	 * @throws LocationException
	 *             Exception for invalid parameters of location
	 * @throws IndexOutOfBoundsException
	 *             Exception for invalid index entry
	 */
	public void updateFloydGraph(Franchise currentFranchise,
			List<Franchise> nearClientStoresList) throws LocationException,
			IndexOutOfBoundsException {

		if (arrayNodes.length == 1) {
			arrayNodes[0] = currentFranchise.getVertex();
			arrayDistances[0][0] = Integer.MAX_VALUE;
		} else {
			// creates a copy of the arrays needed for the algorithm
			int[][] arrayDistancesCopy = new int[arrayDistances.length + 1][arrayDistances.length + 1];
			int[] arrayNodesCopy = new int[arrayNodes.length + 1];

			// increases one element and copy to the arrays
			for (int i = 0; i < arrayDistances.length; i++) {
				for (int j = 0; j < arrayDistances[0].length; j++) {
					arrayDistancesCopy[i][j] = arrayDistances[i][j];
				}
				arrayNodesCopy[i] = arrayNodes[i];
			}
			arrayNodesCopy[arrayNodes.length] = currentFranchise.getVertex();

			// arrow as the infinite distances and updates the node array
			for (int i = 0; i < arrayDistancesCopy.length; i++) {
				Arrays.fill(arrayDistancesCopy[i], Integer.MAX_VALUE);
				arrayNodesCopy[i] = i;
			}

			// mounts the graph with the choice of client
			for (int i = 0; i < nearClientStoresList.size(); i++) {
				int sourceVertex = currentFranchise.getVertex();
				int destinationVertex = nearClientStoresList.get(i).getVertex();
				double distanceBetweenVertex = currentFranchise.getLocation()
						.calculateDistance(
								nearClientStoresList.get(i).getLocation());
				arrayDistancesCopy[sourceVertex][destinationVertex] = (int) distanceBetweenVertex;
				arrayDistancesCopy[destinationVertex][sourceVertex] = (int) distanceBetweenVertex;
			}

			// updates the static arrays
			arrayDistances = new int[arrayDistancesCopy.length][arrayDistancesCopy.length];
			arrayNodes = new int[arrayNodesCopy.length];
			for (int i = 0; i < arrayDistancesCopy.length; i++) {
				for (int j = 0; j < arrayDistancesCopy[0].length; j++) {
					arrayDistances[i][j] = arrayDistancesCopy[i][j];
				}
				arrayNodes[i] = arrayNodesCopy[i];
			}
		}
	}

	/**
	 * Updates the list of all franchises
	 * 
	 * @param listAllFranchises
	 *            The list of all franchises
	 */
	public void updateListAllFranchises(List<Franchise> listAllFranchises) {
		this.listAllFranchises = listAllFranchises;
	}

	/**
	 * Returns next franchise in shortest path
	 * 
	 * @param sourceFranchise
	 *            Source Franchise
	 * @param destinationFranchise
	 *            Destination Franchise
	 * @return next franchise in shortest path
	 */
	public Franchise getNextFranchise(Franchise sourceFranchise,
			Franchise destinationFranchise) {

		calcShortestPaths(arrayNodes, arrayDistances);

		List<Integer> listVertexPath = getShortestPath(sourceFranchise
				.getVertex(), destinationFranchise.getVertex());

		if (listVertexPath.size() == 1) {
			for (Franchise tempFranchise : listAllFranchises)
				if (tempFranchise.getVertex() == listVertexPath.get(0))
					return tempFranchise;
		} else {
			for (Franchise tempFranchise : listAllFranchises)
				if (tempFranchise.getVertex() == listVertexPath.get(1))
					return tempFranchise;
		}

		return null;
	}

}
